package com.yehui.algorithm.sword;

import java.util.ArrayList;

/**
 * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 * Created by XuChunH on 2016/9/16.
 */
public class GetLeastNumbers {
    public ArrayList<Integer> getLeastNumbers(int [] input, int k) {
        if(input == null || input.length == 0 || input.length < k){
            return new ArrayList<Integer>();
        }

        ArrayList<Integer> result = new ArrayList<>();
        for (int i = (k - 1) / 2; i >= 0; i--) {
            adjust(input, i, k - 1);
        }
        for (int i = k; i < input.length; i++) {
            if(input[i] < input[0]){
                swap(input, 0, i);
                adjust(input, 0, k - 1);
            }
        }
        for (int i = k - 1; i > 0; i--) {
            swap(input, 0, i);
            adjust(input, 0, i - 1);
        }
        for (int i = 0; i < k; i++) {
            result.add(input[i]);
        }
        return result;
    }

    private void adjust(int[] array, int start, int end){
        int temp = array[start];
        for (int i = 2 * start + 1; i <= end; i = 2 * i + 1) {
            if(i < end) {
                i = array[i] < array[i + 1] ? i + 1 : i;
            }
            if(array[i] < temp) {
                break;
            }
            array[start] = array[i];
            start = i;
        }
        array[start] = temp;
    }

    private void swap(int[] array, int m, int n){
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }
}
